#include <vector>
#include<Windows.h>
using std::vector;
#define MAP_ROW 6
#define MAP_COL 8
struct MyPoint
{
	int row, col;
};
enum PathDir { p_up, p_donw, p_left, p_right };
struct PathData
{
	int val;
	PathDir dir;
	bool isFind;
};
struct MyPathNode
{
	MyPoint pos;
	MyPathNode* parent;
	vector<MyPathNode*> child;
};
void clearTree(MyPathNode*& root)
{
	if (root)
	{
		for (size_t i = 0; i < root->child.size(); ++i)
			clearTree(root->child[i]);
		delete root;
		root = nullptr;
	}
}
bool isCheckPoint(MyPoint const& pos, PathData arr[][MAP_COL])
{
	if (pos.row >= 0 && pos.row < MAP_ROW && pos.col >= 0 && pos.col < MAP_COL)
	{
		if (arr[pos.row][pos.col].val == 0
			&& arr[pos.row][pos.col].isFind == false)
			return true;
	}
	return false;
}
int main(int argc, TCHAR* argv[])
{
	int arr[MAP_ROW][MAP_COL] = {
	{ 0, 0, 0, 0, 0, 0, 0, 0 },
	{ 0, 0, 0, 0, 0, 0, 0, 0 },
	{ 0, 1, 1, 0, 0, 0, 0, 0 },
	{ 0, 0, 0, 0, 0, 0, 0, 0 },
	{ 0, 0, 0, 0, 0, 0, 0, 0 },
	{ 0, 0, 0, 0, 0, 0, 1, 0 }
	};
	PathData pathArr[MAP_ROW][MAP_COL];
	for (int i = 0; i < MAP_ROW; ++i)
	{
		for (int j = 0; j < MAP_COL; ++j)
		{
			pathArr[i][j].val = arr[i][j];
			pathArr[i][j].dir = p_up;
			pathArr[i][j].isFind = false;
		}
	}
	MyPoint beginPoint = { 1, 1 };
	MyPoint endPoint = { 5, 7 };
	pathArr[beginPoint.row][beginPoint.col].isFind = true;
	MyPathNode* pRoot = nullptr;
	pRoot = new MyPathNode;
	pRoot->pos = beginPoint;
	pRoot->parent = nullptr;
	vector<MyPathNode*> nodeList;
	vector<MyPathNode*> tempNodeList;
	nodeList.push_back(pRoot);
	MyPoint tempPoint;
	while (true)
	{
		for (int i = 0; i < (int)nodeList.size(); ++i)
		{
			for (int j = 0; j < 4; ++j)
			{
				tempPoint = nodeList[i]->pos;
				switch (j)
				{
				case p_up:
					tempPoint.row--;
					break;
				case p_donw:
					tempPoint.row++;
					break;
				case p_left:
					tempPoint.col--;
					break;
				case p_right:
					tempPoint.col++;
					break;
				}
				if (isCheckPoint(tempPoint, pathArr))
				{
					MyPathNode* tempNode = new MyPathNode;
					tempNode->pos = tempPoint;
					tempNode->parent = nodeList[i];
					nodeList[i]->child.push_back(tempNode);
					pathArr[tempNode->pos.row][tempPoint.col].isFind = true;
					tempNodeList.push_back(tempNode);
					if (tempPoint.row == endPoint.row && tempPoint.col ==
						endPoint.col)
					{
						MyPathNode* pNode = tempNode;
						while (pNode)
						{
							printf("row = %d,col = %d\n", pNode->pos.row, pNode -> pos.col);
							pNode = pNode->parent;
						}
						goto OVERTAB;
					}
				}
			}
		}
		if (tempNodeList.size() == 0)
			goto OVERTAB;
		nodeList = tempNodeList;
		tempNodeList.clear();
	}
OVERTAB:
	clearTree(pRoot);
	return 0;
}